package com.mgq.algorithm.dabiaofa;

/**
 * 小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个
 * 每袋的包装包装不可拆分。可是小虎现在只想购买恰好n个苹果，小虎想购买尽
 * 量少的袋数方便携带。如果不能购买恰好n个苹果，小虎将不会购买。输入- -个
 * 整数n，表示小虎想购买的个苹果，返回最小使用多少袋子。如果无论如何都不
 * 能正好装下，返回-1。
 */
public class AppleBag {

    public static int getMinBag(int n) {
        int bag6 = -1;
        int bag8 = n / 8;
        int rest = n - (bag8 * 8);
        //优先使用8的袋子
        while (bag8 >=0 && rest < 24) {
            //剩余的6能装完,就用6装
            int restUse6 = (rest % 6 == 0) ? (rest / 6) : -1;
            if (restUse6 != -1) {
                bag6 = restUse6;
                break;
            }
            //不能装, 8袋子减去一个,继续用6尝试
            bag8--;
            rest = n - bag8 * 8;
        }
        return bag6 == -1 ? -1 : bag8 + bag6;
    }

    /**
     * 方法二: 使用打表法
     * 打表法其实就是在方法一的基础上,直接找出数学规律.直接利用数学原理写出答案
     * 我们发现当n从12开始时, 都呈现了规律 3,-1,3,-1,3,-1,3,-1
     *                               4,-1,4,-1,4,-1,4,-1
     *                               5,-1,5,-1,5,-1,5,-1
     * @param n
     * @return
     */
    public static int getMinBag2(int n) {
        //奇数
        if ((n & 1) != 0) {
            return -1;
        }
        if (n < 18) {
            if (n == 6 || n == 8) {
                return 1;
            }
            if (n ==12||n==14||n==16) {
                return 2;
            }
            return -1;
        }
        return (n-18)/8+3;
    }

    public static void main(String[] args) {
/*
        System.out.println(11&1);
        System.out.println(7&1);
        System.out.println(17&1);
        System.out.println(27&1);
        System.out.println(3&1);*/

        // System.out.println(getMinBag(10));
        for (int i = 1; i < 101; i++) {
            System.out.println("n1=" + i + ": " + getMinBag(i));
           // System.out.println("n2=" + i + ": " + getMinBag2(i));
        }

    }
    /**
     * n=1: -1
     * n=2: -1
     * n=3: -1
     * n=4: -1
     * n=5: -1
     * n=6: 1
     * n=7: -1
     * n=8: 1
     * n=9: -1
     * n=10: -1
     * n=11: -1
     * n=12: 2
     * n=13: -1
     * n=14: 2
     * n=15: -1
     * n=16: 2
     * n=17: -1
     * n=18: 3
     * n=19: -1
     * n=20: 3
     * n=21: -1
     * n=22: 3
     * n=23: -1
     * n=24: 3
     * n=25: -1
     * n=26: 4
     * n=27: -1
     * n=28: 4
     * n=29: -1
     * n=30: 4
     * n=31: -1
     * n=32: 4
     * n=33: -1
     */
}
